#include <stdio.h>

void Swap(int* p1, int* p2)
{
	int tem = *p1;
	*p1 = *p2;
	*p2 = tem;
}

// 排升序
void QuickSort(int* a, int left, int right)
{
	if (left >= right)
		return;
	int key = left;
	int begin = left, end = right;
	while (begin < end)
	{
		// 从右往左开始找小
		while (begin < end && a[end] >= a[key])
			--end;
		while (begin < end && a[begin] <= a[key])
			++begin;
		Swap(&a[begin], &a[end]);
	}
	Swap(&a[key], &a[begin]);
	key = begin;
	QuickSort(a, left, key - 1);
	QuickSort(a, key + 1, right);
}

// 前后指针
void QuickSort2(int* a, int left, int right)
{
	if (left >= right)
		return;
	int prev = left, cur = left + 1;
	int key = left;
	while (cur <= right)
	{
		if (a[cur] < a[key])
		{
			if (++prev != cur)
				Swap(&a[prev], &a[cur]);
		}
		cur++;
	}
	Swap(&a[key], &a[prev]);
	key = prev;
	QuickSort2(a, left, prev - 1);
	QuickSort2(a, prev + 1, right);
}

void Print(int* a, int n)
{
	for (int i = 0; i < n; i++)
		printf("%d ", a[i]);
	printf("\n");
}

int main()
{
	int arr[10] = { 5,6,3,5,6,8,2,7,1,9};
	QuickSort2(arr, 0, 9);
	Print(arr, 10);
	return 0;
}